package sysu.el.graph.undi;

import sysu.el.array.ints.ArrInt;
import sysu.el.graph.GTMatrix;
import sysu.el.graph.GraphConstants;
import sysu.el.graph.Path;

public class UndiDCG extends UndiGTMatrix{
	public int midPoint[][];
	public UndiDCG(GTMatrix min_graph){
		super(min_graph.getNodeNum(), min_graph.w);
		this.midPoint = new int[min_graph.getNodeNum()][min_graph.getNodeNum()];
		this.calDCG();
	}
	
	public Path getPath(int i, int j){
		int next = this.midPoint[i][j];
		if (next == GraphConstants.NULL_NODE)
			return Path.NULL;
		
		Path path = new Path(this.getNodeNum());
		path.add(i);
		path.add(next);
		while (next != j) {
			path.add(this.midPoint[next][j]);
			next = this.midPoint[next][j];
		}
//		path.add(j);
		return path;
	}
	
	public boolean existPath(int i, int j){
		return this.midPoint[i][j] != GraphConstants.NULL_NODE;
	}
	
	public boolean existPath(ArrInt path){
		return path.counter < 2;
	}
	
	public boolean isRealPath(ArrInt path){
		return ((Path)path).isRealPath();
	}
	
	public boolean isVirtualPath(ArrInt path){
		return ((Path) path).isVirtualPath();
	}
	
	public void calDCG(){
		UndiDCG.calDCG(this.getNodeNum(), this.w, this.midPoint);
	}
	
	public static void calDCG(int num, int w[][], int midPoint[][]){
		// MidPoint is not unique
		for (int i=0; i<num; i++){
			// Self-Ring
			if (w[i][i] == GraphConstants.NULL_EDGE)
				midPoint[i][i] = GraphConstants.NULL_NODE;
			else midPoint[i][i] = i;
			
			for (int j=i+1; j<num; j++)
				if (w[i][j] != GraphConstants.NULL_EDGE){
					midPoint[i][j] = j;
					midPoint[j][i] = i;
				}else{
					midPoint[i][j] = GraphConstants.NULL_NODE;
					midPoint[j][i] = GraphConstants.NULL_NODE;
				}
		}
		
		// Todo: Solve the shortest ring problem
		for (int k=0; k<num; k++)
			for (int i=0; i<num; i++)
				for (int j=i+1; j<num; j++){
					// To ensure protection on midPoint
//					if ((i==k)||(j==k))
//						continue;
					if ((w[i][k] == GraphConstants.NULL_EDGE)
							||(w[k][j] == GraphConstants.NULL_EDGE))
						continue;
					int tmp = w[i][k] + w[k][j];
					if ((w[i][j] == GraphConstants.NULL_EDGE)||(w[i][j] > tmp)){
						w[i][j] = tmp;
						w[j][i] = tmp;
						midPoint[i][j] = midPoint[i][k];
						midPoint[j][i] = midPoint[j][k];
					}
				}
	}

}
